package com.example.leetdemo.plan1;

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;

public class Sword045 {
    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public int findBottomLeftValue(TreeNode root) {
        int temp = root.val;
        int height = 0;
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        Map<TreeNode, Integer> map = new HashMap<>();
        map.put(root, 0);
        while (queue.size() > 0) {
            TreeNode t = queue.poll();
            int th = map.get(t);
            if (t.left != null) {
                map.put(t.left, th + 1);
                if (th + 1 > height) {
                    height++;
                    temp = t.left.val;
                }
                queue.offer(t.left);
            }
            if (t.right != null) {
                map.put(t.right, th + 1);
                if (th + 1 > height) {
                    height++;
                    temp = t.right.val;
                }
                queue.offer(t.right);
            }
        }
        return temp;
    }
}
